<!DOCTYPE html>
    <html>
    <head>
        <meta charset="UTF-8">
        <title>拓扑排序</title>
        <style>
</style>
        
        <link rel="stylesheet" href="https://cdn.jsdelivr.net/gh/Microsoft/vscode/extensions/markdown-language-features/media/markdown.css">
<link rel="stylesheet" href="https://cdn.jsdelivr.net/gh/Microsoft/vscode/extensions/markdown-language-features/media/highlight.css">
<style>
            body {
                font-family: -apple-system, BlinkMacSystemFont, 'Segoe WPC', 'Segoe UI', system-ui, 'Ubuntu', 'Droid Sans', sans-serif;
                font-size: 14px;
                line-height: 1.6;
            }
        </style>
        <style>
.task-list-item { list-style-type: none; } .task-list-item-checkbox { margin-left: -20px; vertical-align: middle; }
</style>
        
        
        
    </head>
    <body class="vscode-light">
        <h1 id="拓扑排序">拓扑排序</h1>
<h1 id="1-拓扑排序">1. 拓扑排序</h1>
<ul>
<li><a href="https://www.youtube.com/watch?v=ddTC4Zovtbc&amp;list=PLrmLmBdmIlpu2f2g8ltqaaCZiq6GJvl1j">https://www.youtube.com/watch?v=ddTC4Zovtbc&amp;list=PLrmLmBdmIlpu2f2g8ltqaaCZiq6GJvl1j</a></li>
</ul>
<p>这好像不是topo排序啊？</p>
<pre><code><code><div>while 还有点没有加入visited:
    随机选择一个未加入visited的node
    dfs(node)
        将这node加入visited
        dfs(遍历这个点的所有children)
        将这个node加入 结果队列

</div></code></code></pre>
<p><img src="file:///e:\gitee\leetcode\graph\pics\sort1.png" alt="sort1.png"></p>
<p>这个算法还是不能解决有环的情况</p>
<pre><code class="language-java"><div>ublic <span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">TopologicalSort</span>&lt;<span class="hljs-title">T</span>&gt; </span>{

    <span class="hljs-comment">/**
     * Main method to be invoked to do topological sorting.
     */</span>
    <span class="hljs-keyword">public</span> Deque&lt;Vertex&lt;T&gt;&gt; topSort(Graph&lt;T&gt; graph) {
        Deque&lt;Vertex&lt;T&gt;&gt; stack = <span class="hljs-keyword">new</span> ArrayDeque&lt;&gt;();
        Set&lt;Vertex&lt;T&gt;&gt; visited = <span class="hljs-keyword">new</span> HashSet&lt;&gt;();
        <span class="hljs-keyword">for</span> (Vertex&lt;T&gt; vertex : graph.getAllVertex()) {
            <span class="hljs-keyword">if</span> (visited.contains(vertex)) {
                <span class="hljs-keyword">continue</span>;
            }
            topSortUtil(vertex,stack,visited);
        }
        <span class="hljs-keyword">return</span> stack;
    }

    <span class="hljs-function"><span class="hljs-keyword">private</span> <span class="hljs-keyword">void</span> <span class="hljs-title">topSortUtil</span><span class="hljs-params">(Vertex&lt;T&gt; vertex, Deque&lt;Vertex&lt;T&gt;&gt; stack,
            Set&lt;Vertex&lt;T&gt;&gt; visited)</span> </span>{
        visited.add(vertex);
        <span class="hljs-keyword">for</span>(Vertex&lt;T&gt; childVertex : vertex.getAdjacentVertexes()){
            <span class="hljs-keyword">if</span>(visited.contains(childVertex)){
                <span class="hljs-keyword">continue</span>;
            }
            topSortUtil(childVertex,stack,visited);
        }
        stack.offerFirst(vertex);
    }
    
    <span class="hljs-function"><span class="hljs-keyword">public</span> <span class="hljs-keyword">static</span> <span class="hljs-keyword">void</span> <span class="hljs-title">main</span><span class="hljs-params">(String args[])</span></span>{
        Graph&lt;Integer&gt; graph = <span class="hljs-keyword">new</span> Graph&lt;&gt;(<span class="hljs-keyword">true</span>);
        graph.addEdge(<span class="hljs-number">1</span>, <span class="hljs-number">3</span>);
        graph.addEdge(<span class="hljs-number">1</span>, <span class="hljs-number">2</span>);
        graph.addEdge(<span class="hljs-number">3</span>, <span class="hljs-number">4</span>);
        graph.addEdge(<span class="hljs-number">5</span>, <span class="hljs-number">6</span>);
        graph.addEdge(<span class="hljs-number">6</span>, <span class="hljs-number">3</span>);
        graph.addEdge(<span class="hljs-number">3</span>, <span class="hljs-number">8</span>);
        graph.addEdge(<span class="hljs-number">8</span>, <span class="hljs-number">11</span>);
        
        TopologicalSort&lt;Integer&gt; sort = <span class="hljs-keyword">new</span> TopologicalSort&lt;Integer&gt;();
        Deque&lt;Vertex&lt;Integer&gt;&gt; result = sort.topSort(graph);
        <span class="hljs-keyword">while</span>(!result.isEmpty()){
            System.out.println(result.poll());
        }
    }
}
</div></code></pre>
<h1 id="2-有向图查环-入度和出度">2. 有向图查环， 入度和出度</h1>
<p>拓扑排序</p>
<ul>
<li><a href="https://en.wikipedia.org/wiki/Topological_sorting">https://en.wikipedia.org/wiki/Topological_sorting</a></li>
<li><a href="https://dl.acm.org/doi/10.1145/368996.369025">https://dl.acm.org/doi/10.1145/368996.369025</a></li>
<li><a href="https://leetcode.com/problems/course-schedule/solution/">https://leetcode.com/problems/course-schedule/solution/</a></li>
</ul>
<p>简单解释</p>
<pre><code><code><div>while:
    选择入度为0的一个点, 将这个点为起点的所有边去掉，同时更新邻接点的入度
    如果没有入度为0的点，就退出
</div></code></code></pre>
<p>详细解释</p>
<pre><code><code><div>L = Empty list that will contain the sorted elements
S = Set of all nodes with no incoming edge

while S is non-empty do
    remove a node n from S
    add n to tail of L
    for each node m with an edge e from n to m do
        remove edge e from the graph
        if m has no other incoming edges then
            insert m into S

if graph has edges then
    return error   (graph has at least one cycle)
else 
    return L   (a topologically sorted order)
</div></code></code></pre>
<p>这个方法用于查环。如果没有环，则退出while以后，应该所有的边都被消去了。</p>
<pre><code class="language-python"><div><span class="hljs-keyword">from</span> collections <span class="hljs-keyword">import</span> defaultdict

<span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">Solution</span>:</span>
    <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">canFinish</span><span class="hljs-params">(self, numCourses: int, prerequisites: List[List[int]])</span> -&gt; bool:</span>
        m = defaultdict(list)
        indegree = defaultdict(int)
        zeros = []
        
        <span class="hljs-keyword">for</span> u, v <span class="hljs-keyword">in</span> prerequisites:
            m[u].append(v)
            indegree[v] += <span class="hljs-number">1</span>
        
        <span class="hljs-keyword">for</span> v <span class="hljs-keyword">in</span> range(numCourses):
            <span class="hljs-keyword">if</span> indegree[v] == <span class="hljs-number">0</span>:
                zeros.append(v)
        
        <span class="hljs-comment">#print(f"{indegree}")</span>
        visited = <span class="hljs-number">0</span>
        <span class="hljs-keyword">while</span> zeros:
            u = zeros.pop(<span class="hljs-number">0</span>)
            neighbors = m[u]
            <span class="hljs-keyword">for</span> neighbor <span class="hljs-keyword">in</span> neighbors:
                indegree[neighbor] -= <span class="hljs-number">1</span>
                <span class="hljs-keyword">if</span> indegree[neighbor] == <span class="hljs-number">0</span>:
                    zeros.append(neighbor)
            visited += <span class="hljs-number">1</span>
            <span class="hljs-comment">#print(f"u={u} visited={visited} zeros={zeros} indegree={indegree}")</span>
            
        <span class="hljs-keyword">if</span> visited &lt; numCourses:
            <span class="hljs-keyword">return</span> <span class="hljs-literal">False</span>
        <span class="hljs-keyword">else</span>:
            <span class="hljs-keyword">return</span> <span class="hljs-literal">True</span>
        
</div></code></pre>
<h1 id="3-有向图-dfs检测环-detect-cycle-in-directed-graph-algorithm">3. 有向图 dfs检测环, Detect Cycle in Directed Graph Algorithm</h1>
<ul>
<li><a href="https://www.youtube.com/watch?v=rKQaZuoUR4M&amp;list=PLrmLmBdmIlpu2f2g8ltqaaCZiq6GJvl1j&amp;index=10">https://www.youtube.com/watch?v=rKQaZuoUR4M&amp;list=PLrmLmBdmIlpu2f2g8ltqaaCZiq6GJvl1j&amp;index=10</a></li>
<li><a href="https://github.com/mission-peace/interview/blob/master/src/com/interview/graph/CycleInDirectedGraph.java">https://github.com/mission-peace/interview/blob/master/src/com/interview/graph/CycleInDirectedGraph.java</a></li>
</ul>
<p>有向图dfs查环和无向dfs图查环，代码是不一样的。 假设有向图只有两条边，两个点。  [0-&gt;1, 1-&gt;0], 用无向图dfs查环的方法是查不出来的</p>
<p><img src="file:///e:\gitee\leetcode\graph\pics\sort2.png" alt="sort2.png"></p>
<ol>
<li>初始时刻，所有端点都在whitelist里面，</li>
<li>dfs遍历过程中的点都在graylist里面</li>
<li>dfs遍历完成的点放到blacklist里面</li>
</ol>
<p>如果dfs遍历过程中，发现下一个点在graylist里面，就是有环。 上图中还用一个 parent map记录了遍历时刻的顺序。</p>
<ul>
<li>LC 207. Course Schedule</li>
<li><a href="https://leetcode.com/problems/course-schedule/">https://leetcode.com/problems/course-schedule/</a></li>
</ul>
<pre><code class="language-python"><div><span class="hljs-keyword">from</span> collections <span class="hljs-keyword">import</span> defaultdict

<span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">Solution</span>:</span>
    <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">canFinish</span><span class="hljs-params">(self, numCourses: int, prerequisites: List[List[int]])</span> -&gt; bool:</span>
        m = defaultdict(list)

        <span class="hljs-keyword">for</span> u, v <span class="hljs-keyword">in</span> prerequisites:
            m[u].append(v)
            
        status = defaultdict(int)  <span class="hljs-comment"># 0: while, 1:gray, 2:black</span>
        
        <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">dfs</span><span class="hljs-params">(i)</span>:</span>  <span class="hljs-comment"># if cycle loop exists, return True</span>
            <span class="hljs-keyword">if</span> status[i] == <span class="hljs-number">2</span>:
                <span class="hljs-keyword">return</span> <span class="hljs-literal">False</span>

            status[i] = <span class="hljs-number">1</span>
            
            neighbors = m[i]
            <span class="hljs-keyword">for</span> neighbor <span class="hljs-keyword">in</span> neighbors:
                <span class="hljs-keyword">if</span> status[neighbor] == <span class="hljs-number">1</span>:
                    <span class="hljs-keyword">return</span> <span class="hljs-literal">True</span>
                flag = dfs(neighbor)
                <span class="hljs-keyword">if</span> flag:
                    <span class="hljs-keyword">return</span> <span class="hljs-literal">True</span>
                
            status[i] = <span class="hljs-number">2</span>
            <span class="hljs-keyword">return</span> <span class="hljs-literal">False</span>
        
            
        
        <span class="hljs-keyword">for</span> i <span class="hljs-keyword">in</span> range(numCourses):
            <span class="hljs-keyword">if</span> dfs(i):
                <span class="hljs-keyword">return</span> <span class="hljs-literal">False</span>
        <span class="hljs-keyword">return</span> <span class="hljs-literal">True</span>      
</div></code></pre>
<h1 id="4-无向图查环-cycle-in-undirected-graph-graph-algorithm">4. 无向图查环 Cycle in Undirected Graph Graph Algorithm</h1>
<ul>
<li><a href="https://www.youtube.com/watch?v=n_t0a_8H8VY&amp;list=PLrmLmBdmIlpu2f2g8ltqaaCZiq6GJvl1j&amp;index=12">https://www.youtube.com/watch?v=n_t0a_8H8VY&amp;list=PLrmLmBdmIlpu2f2g8ltqaaCZiq6GJvl1j&amp;index=12</a></li>
<li><a href="https://github.com/mission-peace/interview/blob/master/src/com/interview/graph/CycleUndirectedGraph.java">https://github.com/mission-peace/interview/blob/master/src/com/interview/graph/CycleUndirectedGraph.java</a></li>
</ul>
<p>主要是两种方法</p>
<ul>
<li>并查集 disjoint set</li>
<li>dfs</li>
</ul>
<h2 id="disjoint-set">disjoint set</h2>
<pre><code class="language-java"><div>    <span class="hljs-function"><span class="hljs-keyword">public</span> <span class="hljs-keyword">boolean</span> <span class="hljs-title">hasCycleUsingDisjointSets</span><span class="hljs-params">(Graph&lt;T&gt; graph)</span></span>{
        DisjointSet disjointSet = <span class="hljs-keyword">new</span> DisjointSet();
        
        <span class="hljs-keyword">for</span>(Vertex&lt;T&gt; vertex : graph.getAllVertex()){
            disjointSet.makeSet(vertex.getId());
        }
        
        <span class="hljs-keyword">for</span>(Edge&lt;T&gt; edge : graph.getAllEdges()){
            <span class="hljs-keyword">long</span> parent1 = disjointSet.findSet(edge.getVertex1().getId());
            <span class="hljs-keyword">long</span> parent2 = disjointSet.findSet(edge.getVertex2().getId());
            <span class="hljs-keyword">if</span>(parent1 == parent2){
                <span class="hljs-keyword">return</span> <span class="hljs-keyword">true</span>;
            }
            disjointSet.union(edge.getVertex1().getId(), edge.getVertex2().getId());
        }
        <span class="hljs-keyword">return</span> <span class="hljs-keyword">false</span>;
    }
</div></code></pre>
<h2 id="dfs">dfs</h2>
<pre><code class="language-java"><div>    <span class="hljs-function"><span class="hljs-keyword">public</span> <span class="hljs-keyword">boolean</span> <span class="hljs-title">hasCycleDFS</span><span class="hljs-params">(Graph&lt;T&gt; graph)</span></span>{
        Set&lt;Vertex&lt;T&gt;&gt; visited = <span class="hljs-keyword">new</span> HashSet&lt;Vertex&lt;T&gt;&gt;();
        <span class="hljs-keyword">for</span>(Vertex&lt;T&gt; vertex : graph.getAllVertex()){
            <span class="hljs-keyword">if</span>(visited.contains(vertex)){
                <span class="hljs-keyword">continue</span>;
            }
            <span class="hljs-keyword">boolean</span> flag = hasCycleDFSUtil(vertex, visited, <span class="hljs-keyword">null</span>);
            <span class="hljs-keyword">if</span>(flag){
                <span class="hljs-keyword">return</span> <span class="hljs-keyword">true</span>;
            }
        }
        <span class="hljs-keyword">return</span> <span class="hljs-keyword">false</span>;
    }
    
    <span class="hljs-function"><span class="hljs-keyword">public</span> <span class="hljs-keyword">boolean</span> <span class="hljs-title">hasCycleDFSUtil</span><span class="hljs-params">(Vertex&lt;T&gt; vertex, Set&lt;Vertex&lt;T&gt;&gt; visited,Vertex&lt;T&gt; parent)</span></span>{
        visited.add(vertex);
        <span class="hljs-keyword">for</span>(Vertex&lt;T&gt; adj : vertex.getAdjacentVertexes()){
            <span class="hljs-keyword">if</span>(adj.equals(parent)){
                <span class="hljs-keyword">continue</span>;
            }
            <span class="hljs-keyword">if</span>(visited.contains(adj)){
                <span class="hljs-keyword">return</span> <span class="hljs-keyword">true</span>;
            }
            <span class="hljs-keyword">boolean</span> hasCycle = hasCycleDFSUtil(adj,visited,vertex);
            <span class="hljs-keyword">if</span>(hasCycle){
                <span class="hljs-keyword">return</span> <span class="hljs-keyword">true</span>;
            }
        }
        <span class="hljs-keyword">return</span> <span class="hljs-keyword">false</span>;
    }
</div></code></pre>

    </body>
    </html>